#include<iostream>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

#include"Stack.h"
#include"Queue.h"


class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        //bit::stack<int, vector<int>> st;
        //bit::stack<int, list<int>> st;
        bit::stack<int> st;

        for (auto& str : tokens)
        {
            if (str == "+"
                || str == "-"
                || str == "*"
                || str == "/")
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                switch (str[0])
                {
                case '+':
                    st.push(left + right);
                    break;
                case '-':
                    st.push(left - right);
                    break;
                case '*':
                    st.push(left * right);
                    break;
                case '/':
                    st.push(left / right);
                    break;
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }

        return st.top();
    }
};


void test_op1()
{
    srand(time(0));
    const int N = 1000000;

    deque<int> dq;
    vector<int> v;

    for (int i = 0; i < N; ++i)
    {
        auto e = rand() + i;
        v.push_back(e);
        dq.push_back(e);
    }

    int begin1 = clock();
    sort(v.begin(), v.end());
    int end1 = clock();

    int begin2 = clock();
    sort(dq.begin(), dq.end());
    int end2 = clock();

    printf("vector:%d\n", end1 - begin1);
    printf("deque:%d\n", end2 - begin2);
}

void test_op2()
{
    srand(time(0));
    const int N = 1000000;

    deque<int> dq1;
    deque<int> dq2;

    for (int i = 0; i < N; ++i)
    {
        auto e = rand() + i;
        dq1.push_back(e);
        dq2.push_back(e);
    }

    int begin1 = clock();
    sort(dq1.begin(), dq1.end());
    int end1 = clock();

    int begin2 = clock();

    // vector
    vector<int> v(dq2.begin(), dq2.end());
    sort(v.begin(), v.end());
    dq2.assign(v.begin(), v.end());
    int end2 = clock();

    printf("deque sort:%d\n", end1 - begin1);
    printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}

void test_queue()
{
    bit::queue<int, list<int>> q;
    q.push(1);
    q.push(3);
    q.push(2);
    q.push(7);
    q.push(5);

    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

int main()
{
    //vector<string> v = { "4","13","5","/","+" };
    //cout << Solution().evalRPN(v) << endl;
    //test_op1();
    //test_op2();
    test_queue();

    return 0;
}